package pers.vic.basics.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Vic.xu
 * @description: 57.插入区间  {@literal https://leetcode-cn.com/problems/insert-interval/}
 * @date: 2020/12/17 0017 16:03
 * @see J0056_M_Merge 也可以用56题的思路合并区间
 */
public class J0057_H_Insert {

    /*
    给出一个无重叠的 ，按照区间起始端点排序的区间列表。
    在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
     */

    /**
     * 如何直接合并新数组 然后直接用56题的合并数组也是可以的，但是总感觉不是这一题想要的解题过程；
     * 于是我开始直接判断各种区间的包含重叠关系，虽然写起来罗里吧嗦，但是效率确还可以，打败99.48%
     */
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0) {
            return new int[][]{newInterval};
        }
        int len = intervals.length;

        //1如果在整个区间的左边
        if (newInterval[1] < intervals[0][0]) {
            int[][] res = new int[len + 1][2];
            res[0] = newInterval;
            System.arraycopy(intervals, 0, res, 1, len);
            return res;
        }
        //2如果整个区间的右边
        if (newInterval[0] > intervals[len - 1][1]) {
            int[][] res = new int[len + 1][2];
            res[len] = newInterval;
            System.arraycopy(intervals, 0, res, 0, len);
            return res;
        }

        //3新插入的数据在整个区间的中间部位
        List<int[]> list = new ArrayList<>();
        //新区间是否已经处理完毕
        boolean handle = false;
        //新区间是否已经加入结果集
        boolean hasAdded = false;
        for (int i = 0; i < len; i++) {
            int[] cur = intervals[i];
            //如果已经处理完插入区间 直接插入后续数据
            if (handle) {
                list.add(cur);
                continue;
            }
            //当前区间 还没有到达插入区间
            if (cur[1] < newInterval[0]) {
                list.add(cur);
                continue;
            }
            //如果插入区间 没有达到当前区间， 如果插入区间还没加入结果集 就加入，平且后续不再判断
            if (cur[0] > newInterval[1]) {
                if (!hasAdded) {
                    list.add(newInterval);
                    hasAdded = true;
                }
                list.add(cur);
                handle = true;
                continue;
            }
            //如果当前区间直接包含新区间 则无视新区间
            if (cur[0] <= newInterval[0] && cur[1] >= newInterval[1]) {
                return intervals;
            }
            //如果当前区间直接被新区间包含 无视当前区间 把插入区间 加入结果集
            if (cur[0] > newInterval[0] && cur[1] < newInterval[1]) {
                if (!hasAdded) {
                    list.add(newInterval);
                    hasAdded = true;
                }
                continue;
            }


            //插入数据的前部分在当前区间
            if (cur[0] <= newInterval[0] && cur[1] >= newInterval[0]) {
                newInterval[0] = cur[0];
                if (!hasAdded) {
                    list.add(newInterval);
                    hasAdded = true;
                }
                continue;
            }
            //插入数据的后半部分在当前区间
            if (cur[0] <= newInterval[1] && cur[1] >= newInterval[1]) {
                newInterval[1] = cur[1];
                if (!hasAdded) {
                    list.add(newInterval);
                    hasAdded = true;
                }
                handle = true;
                continue;
            }

        }

        return list.toArray(new int[0][0]);
    }

    public static int[][] insert2(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0) {
            return new int[][]{newInterval};
        }
        int len = intervals.length;
        int[][] res = new int[len + 1][2];
        res[0] = newInterval;
        System.arraycopy(intervals, 0, res, 1, len);
        List<int[]> list = new ArrayList<>();
        //先按照区间的首位 升序排列
        Arrays.sort(res, (a,b)->{
            return Integer.signum(a[0] - b[0]);
        });
        int[] temp = res[0];
        list.add(temp);

        for (int i = 1; i < res.length; i++) {
            int[] cur = res[i];
            //合并
            if (cur[0]<= temp[1]) {
                //可能被全包含
                temp[1] = Math.max(cur[1], temp[1]);
            }else {
                //不合并
                temp = cur;
                list.add(temp);
            }
        }
        return list.toArray(new int[0][0]);

    }

    public static void main(String[] args) {
        /*
        输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
        输出：[[1,5],[6,9]]
         */
        int[][] intervals = {{1, 3}, {6, 9}};
        int[] newInterval = {2, 5};

        intervals = new int[][]{{1, 5}};
        newInterval = new int[]{0, 6};
        for (int[] ints : insert2(intervals, newInterval)) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("....");
        /*
        输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
        输出：[[1,2],[3,10],[12,16]]
        解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
         */
        int[][] intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval2 = {4, 8};
        for (int[] ints : insert2(intervals2, newInterval2)) {
            System.out.println(Arrays.toString(ints));
        }
    }
}
